package leetcode100;

import java.util.Arrays;

public class lc038 {

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println("Arrays.toString(nums) = " + Arrays.toString(nums));
        int max = new lc038().maxSubArray(nums);
        System.out.println("max = " + max);
    }

    public int maxSubArray(int[] nums) {
        int current=nums[0];
        int max=nums[0];

        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i],current+nums[i]);
            max = Math.max(current,max);
        }
        return max;

    }


    public int maxSubArray222(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        int[] sums = new int[n+1];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i-1]+nums[i-1];
        }
//        System.out.println(Arrays.toString(sums));

        for (int i = 0; i < sums.length-1; i++) {
            for (int j = i+1; j < sums.length; j++) {
                int sum = sums[j]-sums[i];
                max = Math.max(sum,max);
            }
        }
//        System.out.println("max = " + max);
        return max;
    }
}
